package cn.corffen.test.algorithm.java;

public class SortJava {


    public int findKthLargest(int[] numbers, int k) {
        int lo = 0;
        int hi = numbers.length - 1;
        int target = hi - k + 1;
        while (lo < hi) {
            int partition = partition(numbers, lo, hi);
            if (partition == target) {
                return numbers[partition];
            }
            if (partition < target) {
                lo = partition + 1;
            } else {
                hi = partition - 1;
            }
        }
        return numbers[lo];
    }

    private int partition(int[] numbers, int lo, int hi) {
        int i = lo + 1;
        int j = hi;
        while (true) {
            //注意如果是小于等于也要继续往后移动指针
            while (i < hi && numbers[i] <= numbers[lo]) {
                i++;
            }
            while (j > lo && numbers[j] >= numbers[lo]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(numbers, i, j);
        }
        swap(numbers, lo, j);
        return j;
    }

    private void swap(int[] numbers, int i, int j) {
        int temp1 = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp1;
    }
}
